package com.yileiqian.alg;

public class Fibonacci {

	public static long getFibonacciByRecursion(int n) {
		if (n <= 0) {
			return 0;
		} else if (n == 1) {
			return 1;
		} else {
			return getFibonacciByRecursion(n - 1)
					+ getFibonacciByRecursion(n - 2);
		}
	}

	public static long getFibonacciByItr(int n) {
		if (n <= 0) {
			return 0;
		} else if (n == 1) {
			return 1;
		} else {
			long[] array = new long[n];
			array[0] = 0;
			array[1] = 1;
			for (int i = 2; i < array.length; i++) {
				array[i] = array[i - 1] + array[i - 2];
			}
			return array[n - 1] + array[n - 2];
		}
	}

	public static long getFibonacciByTwoVar(int n) {
		if (n <= 0) {
			return 0;
		}
		if (n == 1) {
			return 1;
		}
		int a = 1;
		int b = 1;
		n = n - 2;

		while (n-- != 0) {
			if (a > b) {
				b += a;
			} else {
				a += b;
			}
		}

		return a > b ? a : b;
	}

	public static void main(String args[]) {
		int n = 10;
		System.out.println(getFibonacciByRecursion(n));
		System.out.println(getFibonacciByItr(n));
		System.out.println(getFibonacciByTwoVar(n));
	}
}
